home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 March / macformat-022.iso / Shareware City / Developers / src / out-of-phase-102-c / OutOfPhase 1.02 Source / OutOfPhase Folder / Factoring.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-23  |  7.9 KB  |  244 lines  |  [TEXT/KAHL]
  1. /* Factoring.c */
  2. /*****************************************************************************/
  3. /*                                                                           */
  4. /*    Out Of Phase:  Digital Music Synthesis on General Purpose Computers    */
  5. /*    Copyright (C) 1994  Thomas R. Lawrence                                 */
  6. /*                                                                           */
  7. /*    This program is free software; you can redistribute it and/or modify   */
  8. /*    it under the terms of the GNU General Public License as published by   */
  9. /*    the Free Software Foundation; either version 2 of the License, or      */
  10. /*    (at your option) any later version.                                    */
  11. /*                                                                           */
  12. /*    This program is distributed in the hope that it will be useful,        */
  13. /*    but WITHOUT ANY WARRANTY; without even the implied warranty of         */
  14. /*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          */
  15. /*    GNU General Public License for more details.                           */
  16. /*                                                                           */
  17. /*    You should have received a copy of the GNU General Public License      */
  18. /*    along with this program; if not, write to the Free Software            */
  19. /*    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.              */
  20. /*                                                                           */
  21. /*    Thomas R. Lawrence can be reached at tomlaw@world.std.com.             */
  22. /*                                                                           */
  23. /*****************************************************************************/
  24.  
  25. #include "MiscInfo.h"
  26. #include "Audit.h"
  27. #include "Debug.h"
  28. #include "Definitions.h"
  29.  
  30. #include "Factoring.h"
  31. #include "Memory.h"
  32.  
  33.  
  34. struct FactorRec
  35.     {
  36.         FactorRec*                    Next;
  37.         unsigned long                Number;
  38.     };
  39.  
  40.  
  41. static FactorRec*                        PrimeList;
  42. static FactorRec*                        PrimeTail;
  43. static MyBoolean                        PrimeListFinished;
  44. EXECUTE(static MyBoolean        Initialized = False;)
  45. EXECUTE(static long                    ListLength = 0;)
  46.  
  47.  
  48. /* initialize internal data structures used by factorer */
  49. MyBoolean                            InitializeFactoring(void)
  50.     {
  51.         ERROR(Initialized,PRERR(ForceAbort,"InitializeFactoring:  already initialized"));
  52.         EXECUTE(Initialized = True;)
  53.         EXECUTE(ListLength = 0;)
  54.         PrimeList = NIL;
  55.         PrimeTail = NIL;
  56.         PrimeListFinished = False;
  57.         return True;
  58.     }
  59.  
  60.  
  61. /* dispose of factor stuff */
  62. void                                    ShutdownFactoring(void)
  63.     {
  64.         ERROR(!Initialized,PRERR(ForceAbort,"ShutdownFactoring:  not initialized"));
  65.         DisposeFactorList(PrimeList);
  66.     }
  67.  
  68.  
  69. /* dispose factor list */
  70. void                                    DisposeFactorList(FactorRec* List)
  71.     {
  72.         while (List != NIL)
  73.             {
  74.                 FactorRec*            Temp;
  75.  
  76.                 CheckPtrExistence(List);
  77.                 Temp = List;
  78.                 List = List->Next;
  79.                 ReleasePtr((char*)Temp);
  80.             }
  81.     }
  82.  
  83.  
  84. /* see if a number is prime according to the list.  the prime list is assumed to */
  85. /* be complete enough to test the number.  In other words, the prime after the */
  86. /* last prime in the list must be greater than or equal to the number. */
  87. static MyBoolean            PrimeTest(unsigned long Integer)
  88.     {
  89.         FactorRec*                    Scan;
  90.  
  91.         ERROR(!Initialized,PRERR(ForceAbort,"PrimeTest:  not initialized"));
  92.         Scan = PrimeList;
  93.         while ((Scan != NIL) && (Scan->Number < Integer))
  94.             {
  95.                 /* divide number by a prime.  if the remainder is 0, then they divided */
  96.                 /* evenly and the prime is a factor, so the number isn't prime. */
  97.                 if ((Integer % Scan->Number) == 0)
  98.                     {
  99.                         return False;
  100.                     }
  101.                 Scan = Scan->Next;
  102.             }
  103.         /* if none of the primes less than the number were a factor of the */
  104.         /* number, then it is prime. */
  105.         return True;
  106.     }
  107.  
  108.  
  109. /* extend the prime list by one entry */
  110. static MyBoolean            ExtendPrimeList(void)
  111.     {
  112.         ERROR(!Initialized,PRERR(ForceAbort,"ExtendPrimeList:  not initialized"));
  113.         /* check for special case of putting only even numbered prime (2) on the list */
  114.         if (PrimeList == NIL)
  115.             {
  116.                 /* if there is nothing in the prime number list, put 2 (the first prime) */
  117.                 /* onto the list. */
  118.                 PrimeList = (FactorRec*)AllocPtrCanFail(sizeof(FactorRec),"FactorRec");
  119.                 if (PrimeList != NIL)
  120.                     {
  121.                         PrimeTail = PrimeList;
  122.                         PrimeList->Next = NIL;
  123.                         PrimeList->Number = 2;
  124.                         EXECUTE(ListLength += 1;)
  125.                         return True;
  126.                     }
  127.                  else
  128.                     {
  129.                         return False;
  130.                     }
  131.             }
  132.         else if (!PrimeListFinished)
  133.             {
  134.                 unsigned long                Scan;
  135.  
  136.                 /* looking for the next prime number */
  137.                 /* first, check for the only even numbered prime */
  138.                 if (PrimeTail->Number == 2)
  139.                     {
  140.                         Scan = 3;
  141.                     }
  142.                  else
  143.                     {
  144.                         Scan = PrimeTail->Number + 2;
  145.                     }
  146.                 /* perform scan.  Scan is always an odd number.  So is 0xffffffff, so */
  147.                 /* we just make sure Scan is less than that number. */
  148.                 while (Scan < 0xffffffff)
  149.                     {
  150.                         ERROR((Scan & 1) == 0,PRERR(ForceAbort,
  151.                             "ExtendPrimeList:  testing even number"));
  152.                         /* checking number to see if it is prime */
  153.                         if (PrimeTest(Scan))
  154.                             {
  155.                                 FactorRec*            Temp;
  156.  
  157.                                 /* if number is prime, then we add it to the list */
  158.                                 Temp = (FactorRec*)AllocPtrCanFail(sizeof(FactorRec),"FactorRec");
  159.                                 if (Temp != NIL)
  160.                                     {
  161.                                         Temp->Next = NIL;
  162.                                         Temp->Number = Scan;
  163.                                         PrimeTail->Next = Temp;
  164.                                         PrimeTail = Temp;
  165.                                         EXECUTE(ListLength += 1;)
  166.                                         return True;
  167.                                     }
  168.                                  else
  169.                                     {
  170.                                         return False;
  171.                                     }
  172.                             }
  173.                         Scan += 2; /* don't try even numbers */
  174.                     }
  175.                 /* if we get here, then Scan == 0xffffffff (biggest odd number) */
  176.                 /* if our numbers are so big that we hit the limit of our long integer */
  177.                 /* then indicate that we can't find any more primes */
  178.                 PrimeListFinished = True;
  179.                 return False;
  180.             }
  181.         else
  182.             {
  183.                 /* prime list is finished, so return False indicating another */
  184.                 /* prime couldn't be added to the list */
  185.                 return False;
  186.             }
  187.         EXECUTE(PRERR(ForceAbort,"ExtendPrimeList:  illegal exit"));
  188.     }
  189.  
  190.  
  191. /* find the common factors of two numbers.  the product of the common factors */
  192. /* is returned (i.e. greatest common factor). */
  193. unsigned long                    FindCommonFactors(unsigned long Left, unsigned long Right)
  194.     {
  195.         FactorRec*                    Scan;
  196.         unsigned long                Product;
  197.  
  198.         ERROR(!Initialized,PRERR(ForceAbort,"FindCommonFactors:  not initialized"));
  199.         /* while the end of the prime number list is less than the largest possible */
  200.         /* factor of one of the numbers, and we can make a new prime list entry. */
  201.         /* ideally, we should take square root of our numbers, but that would take */
  202.         /* too long, so division by 2 still saves a lot of time. */
  203.         /* Some day, I should learn Euclid's algorithm. */
  204.      CheckPrimesAgainPoint:
  205.         if ((PrimeTail == NIL) || (PrimeTail->Number < Left / 2)
  206.             || (PrimeTail->Number < Right / 2))
  207.             {
  208.                 if (!ExtendPrimeList())
  209.                     {
  210.                         /* failed, so just continue */
  211.                         goto DoneWithPrimesPoint;
  212.                     }
  213.                 goto CheckPrimesAgainPoint;
  214.             }
  215.      DoneWithPrimesPoint:
  216.         /* initialize list scanning */
  217.         Scan = PrimeList;
  218.         /* product accumulates the common factors */
  219.         Product = 1;
  220.         /* see note above about division by 2 */
  221.         while ((Scan->Number <= Left) && (Scan->Number <= Right))
  222.             {
  223.                 if ((Left % Scan->Number == 0) && (Right % Scan->Number == 0))
  224.                     {
  225.                         /* if the number divides both numbers evenly, then it is */
  226.                         /* a common factor, so we accumulate it into Product and */
  227.                         /* remove it from both numbers */
  228.                         Left = Left / Scan->Number;
  229.                         Right = Right / Scan->Number;
  230.                         Product = Product * Scan->Number;
  231.                     }
  232.                  else
  233.                     {
  234.                         /* if the number isn't a common factor, then we check the next */
  235.                         /* number.  note that we only do this if it isn't a common factor */
  236.                         /* since there might be multiple instances of a given common */
  237.                         /* factor, such as for 2*2*3 & 2*2*7 (i.e. 12 & 28) */
  238.                         Scan = Scan->Next;
  239.                     }
  240.             }
  241.         /* return the common factor product */
  242.         return Product;
  243.     }
  244.